/*
 * @lc app=leetcode.cn id=5 lang=golang
 *
 * [5] 最长回文子串
 */

// @lc code=start
func longestPalindrome(s string) string {
	l := len(s)
	if l < 2 {
		return s
	}

	m := [][]bool{}
	for i := 0; i < l; i++ {
		m = append(m, make([]bool, l))
	}

	start := 0
	length := 0

	for i := 0; i < l; i++ {
		m[i][i] = true
		start = i
		length = 1
	}

	for i := 0; i < l-1; i++ {
		if s[i] == s[i+1] {
			m[i][i+1] = true
			start = i
			length = 2
		}
	}

	for j := 3; j <= l; j++ {
		for i := 0; i <= l-j; i++ {
			if s[i] == s[i+j-1] && m[i+1][i+j-2] == true {
				m[i][i+j-1] = true
				start = i
				length = j
			}
		}
	}

	return s[start : start+length]
}

// @lc code=end

